#include <iostream>
#include <queue>
//用队列实现二叉树的层序遍历
// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
// 使用队列实现二叉树的层序遍历
void TravelQueue(TreeNode* root) {
    if (root == nullptr) return;
    
    std::queue<TreeNode*> queue; // 使用STL队列
    queue.push(root); // 将根节点加入队列
 
    while (!queue.empty()) {
        TreeNode* current = queue.front(); // 获取队列前端节点
        queue.pop(); // 从队列中移除前端节点
        std::cout << current->val << " "; // 输出当前节点的值
 
        if (current->left != nullptr) {
            queue.push(current->left); // 将左子节点加入队列
        }
        if (current->right != nullptr) {
            queue.push(current->right); // 将右子节点加入队列
        }
    }
}
 
int main() {
    // 构建一个简单的二叉树:
    //      1
    //     / \
    //    2   3
    //   / \   \
    //  4   5   6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
 
    std::cout << "二叉树的层序遍历: ";
    TravelQueue(root); // 调用层序遍历函数
    std::cout << std::endl;
 
    return 0;
}